/*
	LRU机制的实现
	用队列来存储cache
	用map来标记key与队列中的elements
*/

package lru

import "container/list"

// Cache类型的定义
type Cache struct {
	maxSize    int64                         // 允许使用的最大内存，0则不做限制
	nSize      int64                         // 已使用的内存
	ll         *list.List                    // 用于实现lru的双向链表
	cache      map[string]*list.Element      // 缓存map
	OnEnvicted func(key string, value Value) // 删除元素时的回调函数
}

// 链表中的数据类型entry
type entry struct {
	key   string
	value Value
}

// Value类型
type Value interface {
	Len() int
}

// 创建Cache
func New(maxSize int64, onEnvicted func(string, Value)) *Cache {
	// TODO: 判断值是否合法
	return &Cache{
		maxSize:    maxSize,
		nSize:      0,
		ll:         list.New(),
		cache:      make(map[string]*list.Element),
		OnEnvicted: onEnvicted,
	}
}

// 查找方法
// 找到对应的链表节点，将该节点移动到队尾
func (c *Cache) Get(key string) (value Value, ok bool) {
	// 查询cache
	if ele, ok := c.cache[key]; ok {
		// 移动到队首
		c.ll.MoveToFront(ele)

		kv := ele.Value.(*entry)
		return kv.value, true
	}

	return
}

// 删除方法
// 缓存淘汰，删除最近最少访问的节点
func (c *Cache) RemoveOldest() {
	// 得到队尾元素，并删除
	ele := c.ll.Back()
	if ele != nil {
		kv := ele.Value.(*entry)
		// 将占用内存减去len
		c.nSize -= int64(kv.value.Len()) + int64(len(kv.key))

		// 删除队列中
		c.ll.Remove(ele)

		// 删除map中
		delete(c.cache, kv.key)

		// 执行钩子函数
		if c.OnEnvicted != nil {
			c.OnEnvicted(kv.key, kv.value)
		}
	}
}

// 新增方法
// 判断key是否存在，如存在，则更新节点的值，并将其移动到队尾
// 如不存在，则在队尾新增
// 如果超出了最大内存，则调用删除，将最近最少访问的节点删除
func (c *Cache) Add(key string, value Value) {
	// 判断key是否存在
	// 如果存在
	if ele, ok := c.cache[key]; ok {
		kv := ele.Value.(*entry)

		// 移到队首
		c.ll.MoveToFront(ele)

		// 长度变化
		c.nSize += int64(value.Len()) - int64(kv.value.Len())

		// 修改Value值
		kv.value = value
	} else {
		// 将元素添加到队首
		ele := c.ll.PushFront(&entry{key: key, value: value})

		// 添加进map
		c.cache[key] = ele

		// 修改长度
		c.nSize += int64(len(key)) + int64(value.Len())
	}

	// 判断是否超过最大内存
	// 超过则进行RemoveOldest操作淘汰缓存
	// maxSize为0的情况则不做限制
	for c.maxSize != 0 && c.nSize > c.maxSize {
		c.RemoveOldest()
	}

}

// 获取队列长度方法
func (c *Cache) LLen() int {
	return c.ll.Len()
}
